import java.util.Arrays;
import java.util.Random;

/**
 * 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，
 * 使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，
 * 并保证奇数和奇数，偶数和偶数之间的相对位置不变。
 *
 * Date: 2022-09-29
 * Time: 9:59
 */

class Solution {
    public static void reOrderArray(int [] array) {
        int k = 0;
        for(int i = 0; i < array.length; ++i) {
            if((array[i] & 1) == 1) {
                // 数组当前下标为奇数 插入到数组的k下标处
                int tmp = array[i];

                int j = i;
                while(j > k) {
                    array[j] = array[j-1];
                    j--;
                }
                array[k++] = tmp;
            }

        }
    }
}

public class Test {
    public static void main(String[] args) {
        Random random = new Random();

        int[] array = new int[10];

        for (int i = 0; i < array.length; i++) {
            array[i] = random.nextInt(100);
        }

        System.out.println(Arrays.toString(array));

        Solution.reOrderArray(array);

        System.out.println(Arrays.toString(array));
    }
}
